class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0]!=0)return -1;
        int ans =Integer.MAX_VALUE;
        boolean[][] visit = new boolean[grid.length][grid[0].length];
        //步数，坐标  
        Queue<Pair<Integer,int[]>> queue = new LinkedList<>();
        int[] dx = {1,0,0,-1,1,1,-1,-1};
        int[] dy = {0,1,-1,0,-1,1,1,-1};
        queue.offer(new Pair<Integer,int[]>(1,new int[]{0,0}));
        visit[0][0] = true;
        while(!queue.isEmpty()){
            int currDepth = queue.peek().getKey();
            int[] currPos = queue.poll().getValue();
            int currx = currPos[0];
            int curry = currPos[1];
            if(currx==grid.length-1&&curry==grid[0].length-1) ans = Math.min(ans, currDepth);
            for(int i=0; i<8; i++){
                int nx = currx+dx[i];
                int ny = curry+dy[i];
                if(nx<0||ny<0||nx>grid.length-1||ny>grid[0].length-1)continue;
                //System.out.println(nx+" "+ny+" "+grid[nx][ny]);
                if(grid[nx][ny]==0&&!visit[nx][ny]){
                    queue.offer(new Pair<Integer,int[]>(currDepth+1, new int[]{nx,ny}));
                    visit[nx][ny] = true;
                }
            }
        }
        return ans==Integer.MAX_VALUE?-1:ans;
    }
}